package com.fucius.study.leetcode;

/**
 * 2. 尾部的零
 * 中文English
 * 设计一个算法，计算出n阶乘中尾部零的个数
 *
 * 样例
 * 样例  1:
 * 	输入: 11
 * 	输出: 2
 *
 * 	样例解释:
 * 	11! = 39916800, 结尾的0有2个。
 *
 * 样例 2:
 * 	输入:  5
 * 	输出: 1
 *
 * 	样例解释:
 * 	5! = 120， 结尾的0有1个。
 *
 * 挑战
 * O(logN)的时间复杂度
 */
public class TrailingZeros {
    /**
     * 尾部的0和5的关系
     * 时间复杂度O(lgN)
     * @param n: An integer
     * @return: An integer, denote the number of trailing zeros in n!
     */
    public long trailingZeros(long n) {
        long result = 0;
        while(n/5>0){
            n=n/5;
            result+=n ;
        }
        return result;
    }
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(new TrailingZeros().trailingZeros(5555550000000L));
        System.out.println("耗时："+(System.currentTimeMillis()-start)+"ms");
    }
}
